#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

from collections import defaultdict
from pprint import pprint

class BellmanException(Exception) : pass

class Bellman:
    def bellman_ford_shortest_path(self, src, edges_list, vertex_num):
        # 求解src到所有其它节点的最短路径

        # self.path_len = [None] * len(vertex_num)
        # self.path_len[src] = 0                   # 到自身的路径为0
        self.path_len = defaultdict(lambda : 99999999) # 初始化为无穷大(不用负数是因为有可能存在负权重)
        self.path_len[src] = 0                         # 到自身的路径为0
        self.edges_list = edges_list

        for i in range(vertex_num):
            is_best = self.one_loop_relax()
            if is_best:
                print('after [%s]th loop, get best path' % (i + 1))
                break

        is_best = self.one_loop_relax()     # one more loop to check negative cycle
        if not is_best:
            raise BellmanException('There is some negative cycle in graph')

        return self.path_len

    def one_loop_relax(self):
        # return is best/ has relaxed
        is_best = True

        for start, end, weight in self.edges_list:
            origin_len = self.path_len[end]
            new_len = self.path_len[start] + weight
            if origin_len > new_len:
                # self.path_len[end] = min(origin_len, new_len)   # try to relax path
                self.path_len[end] = new_len
                is_best = False

        pprint(self.path_len)
        return is_best


def main():
    print("start main")
    s = Bellman()

    edges = [
        [1, 2, 6],
        [1, 3, 5],
        [1, 4, 5],
        [2, 5, -1],
        [3, 2, -2],
        [3, 5, 1],
        [4, 3, -2],
        [4, 6, -1],
        [5, 7, 3],
        [6, 7, 3],
    ]

    negative_cycle_edges = [
        [1, 2, 4],
        [1, 4, 5],
        [2, 4, 5],      # this edge make loop(negative cycle)
        [4, 3, 3],
        [3, 2, -10],
    ]

    # ret = s.bellman_ford_shortest_path(1, edges, 7)
    ret = s.bellman_ford_shortest_path(1, negative_cycle_edges, 7)
    print(ret)

if __name__ == "__main__":
    main()
